package com.chenken;


/**
 * 插入排序-优化1
 * 将交换转为挪动
 * 		1.现将待插入元素备份
 *  	2.头部有序数据中比待插元素大的，都往尾部方向挪动一个元素
 *  	3.将待插入元素放到最终的合适位置
 */
public class InsertionSort2<T extends Comparable<T>> extends Sort<T>{

	@Override
	protected void sort() {
		//	从下标1开始，每一个元素都要往左比较
		for(int begin = 1;begin<arrays.length;begin++) {
			int current = begin;
			T v = arrays[current];//备份
			//	用备份元素不断跟左边的元素比较，看是否小于左边的元素
			while(current > 0 && compare(v, arrays[current-1])<0) {
				arrays[current] = arrays[current-1];//	向尾部挪动一位
				current--;//继续往左走
			}
			arrays[current] = v;
		}
	}

}
